package com.algorithm.tsp;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Pareto local search algorithm for solving TSP
 * @author heaven
 */
import com.problem.tsp.TSPProblem;
import com.util.solution.impl.TSPSolution;;

public class ParetoLocalSearch2 {
	private TSPProblem problem;
	private int run_num;
	public ParetoLocalSearch2(TSPProblem problem, int run_num){
		this.problem = problem;
		this.run_num = run_num;
	}
	public void execute(int iteration){
		long startMili=System.currentTimeMillis();
		List<TSPSolution> startList = new ArrayList<>();
		Iterator<TSPSolution> iter = problem.exSet.getSolutions().iterator();		
		while(iter.hasNext()){
			TSPSolution t = iter.next();
			try {
				startList.add(t.clone());
			} catch (CloneNotSupportedException e) {
				e.printStackTrace();
			}
		}
		for(int i = 0;i<iteration;i++){
			System.out.println("iteration of : "+(i+1));
			this.PLSexecute(startList);
			startList.clear();
			iter = problem.startingSet.getSolutions().iterator();		
			while(iter.hasNext()){
				TSPSolution t = iter.next();
				try {
					startList.add(t.clone());
				} catch (CloneNotSupportedException e) {
					e.printStackTrace();
				}
			}
			//problem.initialCandidateList(startList);
			problem.startingSet.clear();
			
		}
		long endMili=System.currentTimeMillis();
		System.out.println((endMili-startMili)/1000+" s ");
		problem.exSet.saveObjectiveResults("files/results/tsp/pls/"+problem.problem_des+problem.city_num+"/adp_"+problem.problem_des+problem.city_num+"_"+run_num+".txt");
	}
	public void PLSexecute(List<TSPSolution> list){
		Iterator<TSPSolution> iter = list.iterator();
		while(iter.hasNext()){
			TSPSolution s = iter.next();
			this.generateNeighborhood(s);
		}
	}
	/**
	 * generate the neighborhood of s
	 * @param s
	 */
	public void generateNeighborhood(TSPSolution s){
		int [] route = new int[problem.city_num+1];
		for(int i=0;i<problem.city_num;i++) route[i] = s.route[i];
		route[problem.city_num] = route[0];
		int [] pos = new int[problem.city_num];
		problem.calculatePosition(route, pos);
		int pos1 = 0;
		int pos2 = 0;
		for(int k=0;k<problem.city_num;k++){
			int i = k;
			pos1 = i;
			int curIndex = route[i];
			int nextIndex = route[i+1];
			ArrayList<Integer> candidate = problem.candidateList.get(curIndex);
			Iterator<Integer> iter = candidate.iterator();
			while(iter.hasNext()){
				int next = iter.next();
				pos2 = pos[next];
				int curIndex1 = route[pos2];
				int nextIndex1 = route[pos2+1];
				if(curIndex == nextIndex1) continue;
				if(curIndex == curIndex1) continue;
				if(nextIndex == nextIndex1) continue;
				if(curIndex1 == nextIndex) continue;
				int betterTimes = 0;
				TSPSolution solution = new TSPSolution(problem.city_num, problem.obj_num, -1);
				for(int j=0;j<problem.obj_num;j++){
					int gain = problem.disMatrix[j*problem.city_num*problem.city_num+curIndex*problem.city_num+curIndex1] +
							problem.disMatrix[j*problem.city_num*problem.city_num+nextIndex*problem.city_num+nextIndex1] - 
							(problem.disMatrix[j*problem.city_num*problem.city_num+curIndex*problem.city_num+nextIndex]+
							problem.disMatrix[j*problem.city_num*problem.city_num+curIndex1*problem.city_num+nextIndex1]);
					if(gain<0) betterTimes++;
					solution.object_val[j] = s.object_val[j] + gain;
				}
				if(betterTimes==0) continue;
				solution.route = s.route.clone();
				if(problem.exSet.add(solution)){
					problem.converse(pos1, pos2, solution.route, 0);
					problem.startingSet.add(solution);
				}
			}
		}
	}
	public static void main(String []args){
		TSPProblem tsp = new TSPProblem();
		new ParetoLocalSearch2(tsp, 1).execute(600);
	}
}
